/**
 * https://leetcode-cn.com/problems/merge-sorted-array/
 *
 * 输入:
  nums1 = [1,2,3,0,0,0], m = 3
  nums2 = [2,5,6], n = 3
  输出: [1,2,2,3,5,6]

  num1 和 num2 本身都是【有序】的
  初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
  你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 */

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
  // 下标都从【末尾】开始
  int indexOfM = m - 1;
  int indexOfN = n - 1;
  int cur = m + n - 1;

  // 1. 从【后】往【前】遍历2个有序数组，然后同样从【后】往【前】写入到 num1[i]
  while (indexOfM >= 0 && indexOfN >= 0)
  {
    if (nums1[indexOfM] >= nums2[indexOfN])
    {
      nums1[cur--] = nums1[indexOfM--]; // nums1[cur] = nums1[indexOfM]
    }
    else if (nums1[indexOfM] < nums2[indexOfN])
    {
      nums1[cur--] = nums2[indexOfN--]; // nums1[cur] = nums1[indexOfN]
    }
  }

  // 2. nums2 有剩余的，直接拷贝进去
  while (indexOfN >= 0)
    nums1[cur--] = nums2[indexOfN--]; // nums1[cur] = nums2[indexOfN]
}
